package leetcode.editor.cn;

import java.util.HashSet;

//[37]解数独
public class SudokuSolver37 {
    public static void main(String[] args) {
        Solution solution = new SudokuSolver37().new Solution();

    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public void solveSudoku(char[][] board) {
            if (board == null || board.length <= 0) return;
//        solve(board);
//        solve2(board);
            solve3(board, 0, 0);
        }

        /**
         * dfs-->loop--canable number-->next dfs..
         * check 每一个空格的可选数字的数量，排序。（暂时没有排序）
         * <p>
         * 执行用时: 151 ms, 在Sudoku Solver的Java提交中击败了5.62% 的用户
         * 内存消耗: 43.9 MB,击败了5.01% 的Java用户
         *
         * @param board
         * @return
         */
        private boolean solve(char[][] board) {
            for (int i = 0; i < board.length; i++) {
                for (int j = 0; j < board[0].length; j++) {
                    if (board[i][j] == '.') {
                        HashSet<Character> isValid = getValidChars(board, i, j);
                        for (Character anIsValid : isValid) {
                            board[i][j] = anIsValid; //尝试一种可能。
                            if (solve(board)) {
                                return true;
                            } else {
                                //go back 因为。
                                //如果这个选项但是错了 or 完成，那么回溯不影响，for 循环中尝试另一种可能。
                                //只有set . 因为所有操作只是一个数组对象。
                                board[i][j] = '.';
                            }
                        }
                        //9*9 有'.' 不是正确的解，那么返回false
                        return false;
                    }
                }
            }
            return true; //默认 有解
        }
        //get possiable input chars
        private HashSet<Character> getValidChars(char[][] board, int indexRow, int indexCol) {
            HashSet<Character> possableChars = new HashSet<>(12, 1.0f);
            for (char k = '1'; k <= '9'; k++) {
                possableChars.add(k);
            }
            //remove row col chars
            for (int k = 0; k < board.length; k++) {
                char r = board[indexRow][k];
                char c = board[k][indexCol];
                possableChars.remove(r);
                possableChars.remove(c);
            }
            //remove block[3][3] chars
            // 计算子网格的起始行和列
            int startRow = indexRow / 3 * 3;
            int startCol = indexCol / 3 * 3;
            for (int k = startRow; k < startRow + 3; k++) { // 遍历行
                for (int m = startCol; m < startCol + 3; m++) { // 遍历列
                    char b = board[k][m];
                    possableChars.remove(b);
                }
            }
            return possableChars;
        }


        //TODO 练习这个。。。//执行耗时:6 ms,击败了65.04% 的Java用户 ，，内存消耗:40.1 MB,击败了51.90% 的Java用户
        private boolean solve2(char[][] board) {
//          if (row >= board.length || col >= board.length)return false;
            int row = 0, col = 0;
            for (int i = row; i < board.length; i++) {
                for (int j = col; j < board[0].length; j++) {
                    if (board[i][j] == '.') {
                        //可选
                        for (char k = '1'; k <= '9'; k++) {
                            //有效的继续。
                            if (isValid(board, i, j, k)) {
                                //可选有结果。
                                board[i][j] = k;
                                if (solve2(board)) {//next....
                                    return true;
                                } else {//回溯
                                    board[i][j] = '.';
                                }
                            }
                        }
                        return false;
                    }
                }
            }
            return true; //默认 有解
        }

        //代测，剪枝。。 //		执行耗时:5 ms,击败了68.86% 的Java用户 //			内存消耗:40.2 MB,击败了19.21% 的Java用户
        private boolean solve3(char[][] board, int row, int col) {
            if (row >= board.length) return true;// 成功遍历完所有格子

            int nextRow = col == board.length - 1 ? row + 1 : row;
            int nextCol = col == board.length - 1 ? 0 : col + 1;

            if (board[row][col] != '.'){
                return solve3(board,nextRow,nextCol);
            }else {
                for (char k = '1'; k <= '9'; k++) {
                    //有效的继续。
                    if (isValid(board, row, col, k)) {
                        //可选有结果。
                        board[row][col] = k;
                        if (solve3(board, nextRow,nextCol)) {//next....
                            return true;
                        } else {//回溯
                            board[row][col] = '.';//回溯
                        }

                    }
                }
            }

            return false; // 无法填充当前格子，回溯
        }

        //solve2 、solve3 共用。
        private boolean isValid(char[][] board, int indexRow, int indexCol, char k) {
            for (int i = 0; i < 9; i++) {
                if (board[indexRow][i] == k || board[i][indexCol] == k) {
                    return false;
                }
            }

            //remove block[3][3] chars
            // 计算子网格的起始行和列
            int startRow = indexRow / 3 * 3;
            int startCol = indexCol / 3 * 3;
            for (int i = startRow; i < startRow + 3; i++) { // 遍历行
                for (int m = startCol; m < startCol + 3; m++) { // 遍历列
                    if (board[i][m] == k) {
                        return false;
                    }
                }
            }
            return true;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}